package com.shawn.datastructure.array;

import java.util.Arrays;

public class FirstMissingPositive {

	public int firstMissingPositive(int[] nums) {
		if (nums == null || nums.length == 0) {
			return 1;
		}

		Arrays.sort(nums);
		if (nums[0] > 1 || nums[nums.length - 1] <= 0) {
			return 1;
		}
		int re = 1;
		for (int num : nums) {
			if (num == re) {
				re++;
			}
			if (num > re) {
				return re;
			}
		}
		return re;
	}

	public int firstMissingPositive2(int[] A) {
		int i = 0;
		while (i < A.length) {
			while (A[i] > 0 && A[i] < A.length && A[A[i] - 1] != A[i]) {
				swap(A, A[i] - 1, i);
			}
			i++;
		}
		i = 0;
		while (i < A.length && A[i] == i + 1) {
			i++;
		}
		return i + 1;
	}

	private void swap(int[] A, int i, int j) {
		int temp = A[i];
		A[i] = A[j];
		A[j] = temp;
	}

	public static void main(String[] args) {
		FirstMissingPositive firstMissingPositive = new FirstMissingPositive();
		int[] nums = {1,2,0};
		firstMissingPositive.firstMissingPositive2(nums);
	}
}
